/**
 * 
 */
package leetCode;

import java.util.ArrayList;

/**
 * @author zhong
 *
 */
public class LeafSimilarTrees {
	public boolean leafSimilar(TreeNode root1, TreeNode root2) {
		ArrayList<TreeNode> leafSq = getLeafSq(root1);
		ArrayList<TreeNode> leafSq2 = getLeafSq(root2);
		if (leafSq.size() != leafSq2.size()) {
			return false;
		}
		for (int i = 0; i < leafSq.size(); i++) {
			if (leafSq.get(i).val != leafSq2.get(i).val) {
				return false;
			}
		}
		return true;
	}

	private ArrayList<TreeNode> getLeafSq(TreeNode root1) {
		ArrayList<TreeNode> res = new ArrayList<>();
		houxu(root1, res);
		return res;
	}

	private void houxu(TreeNode root1, ArrayList<TreeNode> res) {
		if (root1 == null) {
			return;
		}

		if (root1.left == null && root1.right == null) {
			res.add(root1);
		} else {
			houxu(root1.left, res);
			houxu(root1.right, res);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
